1. Field of the Invention
The present invention relates to a method, an apparatus, and a program for enhancing performance of a parity check in computer-readable media, for example in RAID System.
2. Description of the Related Art
For data security, check codes are added to data on a block by block basis. A block serves as a unit of data input or output to/from a disk. A format of a block has a data area and a block check code (BCC). The BCC contains a block CRC which is obtained by a calculation based on the data, and a block ID (Identify) which is generated from a block address.
In FIG. 8, as a data storage disk configuration, RAID (Redundant Arrays of Inexpensive or Independent Disks) 1 or RAID 5 has been used. In a RAID 1 system, as shown in FIG. 8, identical data are stored on a disk 965 and a disk 964. FIG. 9A illustrates a RAID 4 or 5 system which includes a disk 963, a disk 962, and a disk 961 for storing data, and also includes a disk 960 for storing parity data. Hereinafter, the number of disks for storing data is referred to as “N”, and, including a parity disk, the total number of disks is referred to as “(N+1)”. An example of a RAID configuration shown in FIG. 9A is expressed as RAID (N+1), and in this example the value of “N” is “3”.
FIG. 10 illustrates a relationship between block IDs and data stored on the disk. While block IDs 957 are updated sequentially, one at a time starting from 0, data 956 is stored in a location corresponding to a block ID 957 in hexadecimal digits 956 such as “0”, “4”, “8”, “1”, as shown in FIG. 10. The hexadecimal digits 956 can be expressed in binary 954 as shown below each of the hexadecimal digits 956 in the figure.
FIG. 11 illustrates a relationship between a strip 951, 9512, 9513 and a stripe 950. The stripe 950 has a plurality of strips 951, 9512, 9513. Addresses “00H” to “ffH” (H represents hexadecimal, hereinafter the same) designate data locations in a strip 951, and addresses “100H” to “1ffH” represent the next strip 9512. Such a plurality of strips constitutes a stripe 950.
In a RAID 4 or 5 system, the strips in the stripe 950 are provided with block IDs 957. The block IDs 957 have sequential values in the strip as shown in FIG. 11. For example, a block of data is stored in a location designated as the block ID 957 “00b” (b represents binary, hereinafter the same), and another block of data is stored in a location designated as the block ID 957 “01b”. Likewise, other blocks of data are stored.
A BCC in a parity strip is generated by performing an exclusive OR (XOR) operation between BCCs (Block CRC and Block ID) in data strips. FIG. 12 illustrates a process for generating a parity strip. As illustrated in FIG. 12, an XOR operation is performed between each of the block IDs 957 on the strip 9512, 946, 945, and the resultant value is stored on the parity disk 944. A typical XOR operation is illustrated in FIG. 13. The block IDs on the strip 9431, strip 9432 and strip 9433 are “00b”, “01b”, and “10”, respectively. The XOR operation is carried out in the manner described below.
First, the upper bit “0” of the block ID on the disk 0 and the upper bit “0” of the block ID on the strip 9432 are XORed. The resultant value is “0”. Next, the lower bit “0” of the block ID on the strip 9431 and the lower bit “1” of the block ID on the disk 1 are XORed, and “1” is obtained. Thus, “01b” is obtained from these operations. Then, the obtained “01b” and “10b” of the block ID on the strip 9433 are XORed, resulting in “11b”. This “11b” is stored on the parity strip 9434.
In a RAID “(N+1)” configuration, when “N” is an odd number, parity block IDs in a strip have sequential values. FIG. 14 illustrates a calculation process of parity block IDs when “N” is an odd number, “3” in this example. The first address “000H” on the strip 940 and the first address “100H” on the strip 939 are XORed, and “100H” is obtained. Then, this “100H” and the first address “200H” on the strip 938 are XORed, and “300H” is obtained.
This operation will be described in detail. The leading bits of the above block IDs are “1” and “2”, respectively. Since “1”=“0001b” and “2”=“0010b”, “0011b” is obtained by performing an XOR operation between these values. This resultant “0011b” is represented in hexadecimal as “3”. When “00b” and “00b” are XORed, “00b” is obtained. Therefore, the first block ID on the parity strip 937 is “300H”. Then an XOR operation is performed between the last block ID “0ffH” on the strip 940 and the last address “1ffH” on the strip 939 as shown in FIG. 14. The leading bits “0” and “1” are XORed, and the resultant “1” is obtained. Then, the remaining bits “ffH” and “ffH” are XORed, and the result is “00H”. Therefore, the result of the XOR operation between “0ffH” and “1ffH” is “100H”.
Then, this “100H” and the last block ID “2ffH” on the strip 938 are similarly XORed, and “3ffH” is obtained. Thus, as can be found from the above operation procedure, when “N” is an odd number, the block IDs in the parity strip 937 have sequential values starting from “300H” and ending with “3ffH”.
On the other hand, when N is an even number, block IDs in a parity strip have constant values. For example, when “N”=“2” in a RAID (N+1) system, the disk “0” 951 and the disk “1” 9512 as shown in FIG. 11 are provided and a parity disk 9513. The first block ID “000H” on the strip 951 and the first block ID “100H” on the strip 9512 are XORed, and “100H” is obtained. Then, an XOR operation is performed between the last block IDs “0ffH” on the strip 9512 and the last block IDs “1ffH” on the strip 9512, and thus “100H” is obtained. This “100H” is the same value obtained from the above XOR operation performed between the first block IDs. Therefore, it is found that the block IDs have constant values in a parity strip 9513 for RAID (N+1) when “N” is an even number.
However, since each block ID designates a location of data, the values of the block IDs in the parity strip have to be sequential. When “N” is an odd number, as described above, the parity strip block IDs have sequential values. On the other hand, however, when “N” is an even number, the values of the parity strip block IDs are the same regardless of the block ID values.
For this reason, when “N” is an even number, a virtual data IDs are prepared so that the XOR operations can be performed between even-number of block IDs. This virtual data IDs are referred to as a phantom block IDs. The phantom block ID is used to calculate the parity strip block ID. The parity strip block ID is not created by simple XOR operation when the disks are even number, because the simple XOR operation obtains the parity strip block ID which is not sequential in the parity strip.
A case where a phantom block ID is added to a RAID (N+1) system is illustrated in FIG. 15. In this case, the block IDs on the phantom block IDs are assumed to be “000H” to “0ffH”. When the first block ID “000H” on the phantom block IDs and the first block ID “000H” on the strip 935 are XORed, “000H” is obtained. This obtained “000H” and the first block ID “100H” on the strip 934 are XORed, and “100H” is obtained.
Then, the last block ID “0ffH” on the phantom block IDs 933 and the last block ID “0ffH” on the strip 935 are XORed, and “000H” is obtained. The obtained “000H” and the last block ID “1ffH” on the strip 934 are XORed, and “1ffH” is obtained. This indicates the block IDs on the parity strip 932 have sequential values. Thus, even if “N” is an even number, providing a phantom block IDs causes block IDs to be sequential in a parity strip regardless of the value of “N” being even. In addition, by setting the 512-byte data area of each block in the phantom block IDs to be all “0s”, the necessity for the XOR operation on data areas can be eliminated. This can keep an increase in operational cost for parity generation down to the amount for one additional XOR operation for 8-byte BCCs. For the phantom block CRC section in the 8-byte BCC, a value corresponding to the all “zero” of the 512-byte data is used. For a block ID section, a value such as a value of the leading strip in a stripe is used, for example.
Thus by using phantom block IDs, the values of block IDs in a parity strip are made sequential for an even number of member disks in a RAID configuration. This enables error detection for a parity strip to be performed similarly to that for a data strip.
As implementations of the foregoing operations, several techniques are known. When a logical failure occurs in a disk array apparatus, one of such techniques can be used to identify a magnetic disk drive that has caused the failure and where the error/failure that has not been detected in a data check process (CRC, parity) performed in units of magnetic disk drives (see, for example, Japanese Unexamined Patent Application Publication No. 1998-171608). Another known technique permits detection of a failure in which old data is erroneously read by a disk control unit with low error detection capability, and also permits detection of data errors using appended check codes (see, for example, Japanese Unexamined Patent Application Publication No. 2003-36146).